// https://leetcode.cn/problems/find-k-th-smallest-pair-distance/
// Created by ade on 2022/11/16.
// 数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
// 给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。返回 所有数对距离中 第 k 小的数对距离。
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Solution {
public:
    // 多路并归会超时
    int smallestDistancePair1(vector<int> &nums, int k) {
        sort(nums.begin(), nums.end());
        auto cmp = [&](pair<int, int> &a, pair<int, int> &b) {
            return nums[a.second] - nums[a.first] > nums[b.second] - nums[b.first];
        };
        priority_queue < pair < int, int >, vector < pair < int, int >>, decltype(cmp) > q(cmp);
        for (int i = 0; i < nums.size() - 1; i++) {
            q.push({i, i + 1});
        }
        auto top = q.top();
        while (k > 0) {
            k--;
            top = q.top();
            q.pop();
            if (top.second + 1 <= nums.size() - 1)
                q.push({top.first, top.second + 1});
        }
        return nums[top.second] - nums[top.first];
    }

    // 二分法
    int smallestDistancePair(vector<int> &nums, int k) {
        /*sort(nums.begin(), nums.end());
        int n = nums.size(), left = 0, right = nums.back() - nums.front();
        while (left <= right) {
            int mid = (left + right) / 2;
            int cnt = 0;
            for (int j = 0; j < n; j++) {
                int i = lower_bound(nums.begin(), nums.begin() + j, nums[j] - mid) - nums.begin();
                cnt += j - i;
            }
            if (cnt >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;*/
        sort(nums.begin(), nums.end());
        int n = nums.size(), left = 0, right = nums.back() - nums.front();// left 和right代表的是长度，而不是坐标
        while (left <= right) {
            int mid = (left + right) / 2;
            int count = 0;
            for (int i = 0; i < n; i++) {
                // 这里是精髓，i和j对count的贡献值,以j为右侧终点，距离到达j的 <= mid的
                int j = lower_bound(nums.begin(), nums.begin() + i, nums[i] - mid) - nums.begin();
                count += i - j;
                    // 这种是O(N)会超时
//                for (int j = 0; j < i; j++) {
//                    if (nums[i] - nums[j] <= mid) count++;
//                }
            }
            if (count >= k) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;

    }

};

int main() {
    Solution so;
    vector<int> nums1 = {62, 100, 4};
    cout << so.smallestDistancePair(nums1, 2) << endl;
    return 0;
}